package com.example.Arithmetic.Lettcode;

import com.example.Arithmetic.Arithmetic.TreeNode;

import java.util.LinkedList;
import java.util.concurrent.atomic.AtomicLong;

/**
 * 日期：2023/10/17
 * 时间：11:58
 * 描述：验证二叉树，验证是不是一个有效的二叉搜索树
 * 前一个不能比后一个大
 */
public class E04Lettcode98 {
    //迭代
    public boolean isValidBST1(TreeNode root) {
        TreeNode node = root;
        LinkedList<TreeNode> list = new LinkedList();
        long l = Long.MIN_VALUE;
        while (node != null || !list.isEmpty()) {
            if (node != null) {
                list.push(node);
                node = node.left;
            } else {
                TreeNode<Integer> pop = list.pop();
                if (l >= pop.val) {
                    return false;
                }
                l = pop.val;
                node = node.right;
            }
        }
        return true;
    }

    //递归1,全局变量
    long l = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode<Integer> root) {
        if (root == null) {
            return true;
        }

        boolean a = isValidBST(root.left);
        if (!a) {
            return false;
        }
        if (l >= root.val) {
            return false;
        }
        l = root.val;
        return isValidBST(root.right);
    }

    //    递归2，局部变量共享
    public boolean isValidBST2(TreeNode root) {
        if (root == null) {
            return true;
        }
        return doValid(new AtomicLong(Long.MIN_VALUE), root);
    }

    public boolean doValid(AtomicLong prev, TreeNode<Integer> node) {
        if (node == null) {
            return true;
        }
        boolean a = doValid(prev, node.left);
        if (prev.get() >= node.val) {
            return false;
        }
        prev.set(node.val);
        boolean b = doValid(prev, node.right);
        return a && b;
    }


    //    上下限方式
    public boolean isValidBST3(TreeNode root) {
        return doBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean doBST(TreeNode<Integer> root, long minValue, long maxValue) {
        if (root == null) {
            return true;
        }
        if (minValue >= root.val || maxValue <= root.val) {
            return false;
        }
        boolean a = doBST(root.left, minValue, root.val);
        if (!a){
            return false;
        }
        return doBST(root.right, root.val, maxValue);
    }
}

